#ifndef AVL_H
#define AVL_H
#include <bits/stdc++.h>
using namespace std;

template<typename T>
struct AVLnode {
    T value;   //value 代表AVL树上的数据域
    int height; //height代表的是节点的高度
    AVLnode *lchild, *rchild;
    AVLnode(T temp) : value(temp), height(0), lchild(nullptr), rchild(nullptr) {}
    AVLnode() {
        this->lchild = nullptr;
        this->rchild = nullptr;
        this->height = 0;
    }
};

class AVL
{
    public:
        string res;

        AVL();

        ~AVL();

        void postInorder(AVLnode<pair<string, string> >* &u);

        AVLnode<pair<string, string> > *getRoot();

        string getKey(AVLnode<pair<string, string> > *u);

        string getValue(AVLnode<pair<string, string> > *u);

        AVLnode<pair<string, string> >* leftRotate(AVLnode<pair<string, string> >* u);

        AVLnode<pair<string, string> >* rightRotate(AVLnode<pair<string, string> >* u);

        AVLnode<pair<string, string> >* insert(AVLnode<pair<string, string> >* &u, string key, string value);

        void insert(string key, string value);

        AVLnode<pair<string, string> >* deleteNode(AVLnode<pair<string, string> >* u, string key);

        void deleteNode(string key);

        void search(string key);

//        void dfs(AVLnode<pair<string, string> >* u);

    private:
        AVLnode<pair<string, string> > *root;

        AVLnode<pair<string, string> >* newNode(string key, string value);

        int getHeight(AVLnode<pair<string, string> > *u);

        int getBalenceFactor(AVLnode<pair<string, string> > *u);

        void updataHeight(AVLnode<pair<string, string> > *&u);

        void search(AVLnode<pair<string, string> > *u, string key);
};

#endif // AVL_H


